package com.linwen.excise.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName _236二叉树的最近公共祖先
 * @Description TODO
 * @Author zero
 * @DATE 2024/4/28 1:56 AM
 * @Version 1.0
 */
public class _236二叉树的最近公共祖先 {
    public static void main(String[] args) {
        Integer[] arr = {3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        MyTreeNode p = new MyTreeNode(5);
        MyTreeNode q = new MyTreeNode(1);
        MyTreeNode root = buildTree(arr);
        MyTreeNode myTreeNode = lowestCommonAncestor(root, p, q);
        System.out.println(myTreeNode.value);
    }


    public static MyTreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        Queue<MyTreeNode> rootQueue = new LinkedList<>();
        MyTreeNode root = new MyTreeNode(arr[0]);
        int index = 1;
        rootQueue.add(root);
        while (!rootQueue.isEmpty()) {
            MyTreeNode rootNode = rootQueue.poll();
            if (rootNode != null) {
                if (index < arr.length) {
                    MyTreeNode leftNode = new MyTreeNode(arr[index++]);
                    rootNode.left = leftNode;
                    rootQueue.add(leftNode);
                }
                if (index < arr.length) {
                    MyTreeNode rightNode = new MyTreeNode(arr[index++]);
                    rootNode.right = rightNode;
                    rootQueue.add(rightNode);
                }
            } else {
                index = index + 2;
            }
        }
        return root;
    }

    public static MyTreeNode lowestCommonAncestor(MyTreeNode root, MyTreeNode p, MyTreeNode q) {
        if (root == null || root.value.equals(p.value) || root.value.equals(q.value)) {
            return root;
        }
        MyTreeNode left = lowestCommonAncestor(root.left, p, q);
        MyTreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }
}

class MyTreeNode {
    Integer value;
    MyTreeNode left;
    MyTreeNode right;

    public MyTreeNode(Integer value) {
        this.value = value;
    }
}